package cn.zifangsky.array.questions;

import org.junit.Test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 战斗
 *
 * <p>有一个游戏战斗场景：左右两边各有一定数量战斗力不等（战斗力就是数组中的数值）的小兵，战斗开始的时候左边的小兵永远只会向右前进且不能回头，
 * 右边的小兵永远只会向左前进且不能回头，当两个小兵相遇的时高战斗力的小兵会把低战斗力的给淘汰掉。</p>
 *
 * <p>现用一个数组来表示场上的所有小兵，其中正数代表左变的小兵，负数代表右边的小兵，然后实现一个函数输入这个输入返回战斗结果。</p>
 *
 * <ol>
 *     <li>输入：[5, 10, -5]；结果：[5, 10]</li>
 *     <li>输入：[6, -6]；结果：[ ]</li>
 *     <li>输入：[-1, -2, 3, -4, 5]；结果：[-1, -2, -4, 5]</li>
 * </ol>
 *
 * @author zifangsky
 * @date 2020/7/10
 * @since 1.0.0
 */
public class Problem_005_Fighting {

    /**
     * 测试代码
     */
    @Test
    public void testMethods(){
        int[] arr1 = new int[]{5, 10, -5};
        //结果：[5, 10]
        System.out.println(Arrays.toString(this.fighting(arr1)));

        int[] arr2 = new int[]{6, -6};
        //结果：[]
        System.out.println(Arrays.toString(this.fighting(arr2)));

        int[] arr3 = new int[]{-1, -2, 2, 3, -4, 5};
        //结果：[-1, -2, -4, 5]
        System.out.println(Arrays.toString(this.fighting(arr3)));

        int[] arr4 = new int[]{-3, 4, 3, -1, -4};
        //结果：[-3]
        System.out.println(Arrays.toString(this.fighting(arr4)));

        int[] arr5 = new int[]{6, 4, -5, 3, -2};
        //结果：[6, 3]
        System.out.println(Arrays.toString(this.fighting(arr5)));
    }

    /**
     * Fighting
     */
    private int[] fighting(int[] arr){
        if(arr == null|| arr.length < 1){
            return null;
        }

        //最后存活者
        List<Integer> survivors = new ArrayList<>();
        //用于标识当前存活数组最右侧有没有left小兵
        boolean flag = false;

        //从左往右依次遍历所有小兵
        for(int i = 0; i < arr.length; i++){
            //1. 不处理等于0的元素情况
            if(arr[i] == 0){
                continue;
            }

            //2. 如果当前是left小兵，则直接添加到存活数组
            if(arr[i] > 0){
                survivors.add(arr[i]);
                //更新flag状态
                if(!flag){
                    flag = true;
                }
                continue;
            }

            //3. 如果当前是right小兵，则分两种情况处理：
            //3.1 如果当前存活数组最右侧没有left小兵，则将其添加到存活数组
            if(!flag){
                survivors.add(arr[i]);
            }
            //3.2 否则需要跟left小兵依次战斗
            else{
                //用于标识本次战斗中right小兵获得胜利
                boolean rightWin = false;
                while (survivors.size() > 0){
                    //取出存活数组的最右侧一个元素
                    Integer lastItem = survivors.get(survivors.size() - 1);

                    if(lastItem < 0){
                        break;
                    }
                    //如果当前left小兵胜利，则不再继续战斗
                    else if(lastItem > Math.abs(arr[i])){
                        rightWin = false;
                        break;
                    }

                    //如果平局，则将其从存活数组移除，本次战斗结束
                    else if(lastItem == Math.abs(arr[i])){
                        survivors.remove(survivors.size() - 1);
                        rightWin = false;
                        break;
                    }
                    //否则先将其从存活数组移除，然后让当前right小兵继续跟左边的left小兵战斗
                    else{
                        survivors.remove(survivors.size() - 1);
                        if(!rightWin){
                            rightWin = true;
                        }
                    }
                }

                //将获胜的right小兵添加到存活数组
                if(rightWin){
                    survivors.add(arr[i]);
                }
                //重置flag状态
                if((survivors.size() > 0) && (survivors.get(survivors.size() - 1) < 0)) {
                    flag = false;
                }
            }
        }

        //4. 返回结果
        return survivors.stream().mapToInt(i->i).toArray();
    }

}
